import bisect
from typing import List

# 给定一个整数数组 nums，按要求返回一个新数组counts。
# 数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于nums[i] 的元素的数量。


"""
统计数组中  当前数字右边比它小的
暴力：O(n^2)

"""


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        sortns = []  # 放排序结果
        res = []  # 放坐标结果
        for n in reversed(nums):
            idx = bisect.bisect_left(sortns, n)  # 找到插入位置  如果已经存在相同的数，放在最左边——》第一个大于等于n的  相当于lower_bound
            res.append(idx)  # 插入位置就是当前位置的结果
            sortns.insert(idx, n)
        return res[::-1]


if __name__ == '__main__':
    sol = Solution()
    print(sol.countSmaller([5, 2, 6, 1]))
